#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    static vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        int flag = 0;
        for(int i = 0; i < nums.size()-2 && nums[i] <= 0; i++)
        {
            //逻辑：
            //先固定一个数，用这个数确定一个目标值
            //后续使用双指针的思路来寻找和为目标值的两个值
            //关键：
            //1、去重：通过前后对比两个值，假如相同就不需要继续比较
            //2、不漏
            while(i != 0 && nums[i] == nums[i-1] && i < nums.size()-2) i++;
            if(flag) break;
            int left = i + 1;
            int right = nums.size()-1;
            int target = -nums[i];
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum < target)
                {
                    left++;
                }
                else if(sum > target)
                {
                    right--;
                }
                else if(sum == target) 
                {
                    if(nums[left] == nums[left-1] && left != i + 1 && 
                       nums[right] == nums[right+1] && right != nums.size()-1 && 
                       left < right)
                    {
                        while(nums[left] == nums[left-1] && left != i + 1 && left < right) left++;
                        while(nums[right] == nums[right+1] && right != nums.size()-1 && left < right) right--;
                    }
                    else ret.push_back({nums[i], nums[left++], nums[right--]});
                }
            }
        } 
        return ret;       
    }
};

int main()
{
    // vector<int> vc = {-1,0,1,2,-1,-4};
    vector<int> vc = {0, 0, 0, 0};
    auto ans = Solution::threeSum(vc);
    for(auto it: ans)
    {
        for(auto i: it)
        {
            cout << i << " "; 
        }
        cout << endl;
    }
    return 0;
}